public class BinaryTree {
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

    }

    public boolean isSameTree1(TreeNode p, TreeNode q) {
        //1.先判断两棵树的结构是否相同
        if(p!=null&&q==null||p==null&&q!=null){
            return false;
        }

        //2.上面的if语句没有执行，意味着两个引用 同时为空 ，或者同时不为空
        if(p==null&&q==null){
            return true;
        }

        //3.都不为空，则判断值是否相同
        if(p.val != q.val){
            return false;
        }

        //4.走到这，说明当前遍历的节点位置和值都相同，同时递归左右树
        return isSameTree1(p.left,q.left) && isSameTree1(p.right,q.right);

        //5.巧妙利用递归的返回值，作为总递归的返回值
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null) return false; //防止下面递归，新的root为空触发空指针异常

        if(isSameTree(root,subRoot)) return true;//调用第一题写的方法

        if(isSubtree(root.left,subRoot)) return true; //递归root左子树和subRoot的比较

        if(isSubtree(root.right,subRoot)) return true;//递归root右子树和subRoot的比较
        return false;
        
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.先判断两棵树的结构是否相同
        if(p!=null&&q==null||p==null&&q!=null){
            return false;
        }

        //2.上面的if语句没有执行，意味着两个引用 同时为空 ，或者同时不为空
        if(p==null&&q==null){
            return true;
        }

        //3.都不为空，则判断值是否相同
        if(p.val != q.val){
            return false;
        }

        //4.走到这，说明当前遍历的节点位置和值都相同，同时递归左右树
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);

        //5.巧妙利用递归的返回值，作为总递归的返回值
    }

    TreeNode prev=null;

    public void ConvertChild(TreeNode root){
        if(root==null)return ;
        ConvertChild(root.left);
        //接下来，在中间的地方对节点进行调整

        root.left=prev;

        if(prev!=null) prev.right=root;

        prev=root;


        ConvertChild(root.right);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)return null;

        ConvertChild(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;
    }

    public boolean isSymmetric(TreeNode root) {
        //根节点为空，也是对称二叉树
        if(root==null)return true;

        //不为空，以isisSymmetricChild()的返回值，作为isSymmetric()的返回值
        return isSymmetricChild(root.left,root.right);
    }

    private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {

        //1.先判断当前root的左右节点的结构和值是否相同
        if(leftTree==null&&rightTree==null)return true;

        //2.结构不同的情况，一定要处理，便于递归回溯
        if(leftTree!=null&&rightTree==null||leftTree==null&&rightTree!=null)return false;

        //3.结构相同，但是值不相同的情况
        if(leftTree.val!=rightTree.val)return false;

        //4.结构相同，值也相同，才可以递归，通过下次递归回溯的返回值，作为本次递归的返回值

        //5.不但左树的左树与右树的右树比较，左树的右树和右树的左树比较，结构和值都要相同
        return isSymmetricChild(leftTree.left,rightTree.right)&&
                isSymmetricChild(leftTree.right,rightTree.left);
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;

        int d=Math.abs(getHeight(root.left)-getHeight(root.right));

        if(d<=1&&isBalanced(root.left)&&isBalanced(root.right))return true;

        return false;
    }

    public int getHeight(TreeNode root){

        if(root==null)return 0;

        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }
}
